This invention relates to the field of geometric modeling and smoothing models using fairing operators.
In recent years, models of graphics applications are becoming more complex. Recent trends in graphics visualization include an increasing complexity of datatests, increasing sophistication of computational models, real time performance and scalability, interactive exploration and analysis, and quantitative analysis and error control. Driven by the need to manage model complexity there has been a convergence of graphics and modeling technologies. The design of multi-resolution mesh representations of three-dimensional models is no exception. Two different types three-dimensional models are manifold and non-manifold models.
These models are based on the principles of Euclidean geometry and specifically, Euclidean space. A manifold, in general, is defined as a topological space in which every point has a neighborhood that is homeomorphic to the interior of a sphere in Euclidean space of the same number of dimensions. Being homeomorphic means that there exists a one-to-one mapping between sets (in this case, a neighborhood and the interior of a sphere) such that both the function and its inverse are continuous and that topology exists for geometric figures which can be transformed one into the other by an elastic deformation. A basic non-manifold model (12) is shown in FIG. 2A and a two-manifold model (10) is shown in FIG. 2B. A surface is two-manifold (10) if all of it points have an open neighborhood homeomorphic to 2. This definition can be extended to two-manifold surfaces with boundaries, where every point has an open neighborhood homeomorphic to either 2 or +2. If a surface does not satisfy these criteria, then it is called a non-manifold (12) as represented by a horizontal and a vertical surface together in FIG. 2A. Examples of non-manifold surfaces (12) include, for instance, self-intersecting surfaces or T-junctions. Most of the following research is directed toward the handling of arbitrary, two-manifold models (10). Research has not been directed towards the handling of non-manifold models (12).
Two key ingredients in the design of multi-resolution mesh representations include 1) a fairing or subdivision method and 2) a mesh simplification algorithm.
A subdivision method starts with a triangle mesh. The mesh is refined by subdivision and the mesh is smoothed by moving vertices. This method is accomplished by generating infinite subdivisions. In signal processing terms, it is upsampling followed by relaxation. An example of a subdivision method is Loop subdivision for the estimation of high resolution mesh from the simplified representation. See, D. Zorin, P. Schrxc3x6der, and W. Sweldens, xe2x80x9cInteractive Multiresolution Mesh Editingxe2x80x9d, 1995.
A fairing method is a process of removing high frequency components from geometry. Fairing is an extension of low pass filtering in signal processing to meshes. An example of a fairing method is devised by L. Kobbelt, who is the first to demonstrate the advantages of discrete fairing method as a fairing operator for mesh editing. He combines a very fast multilevel smoother with a progressive mesh simplification algorithm. See L. Kobbelt, xe2x80x9cInteractive Multi-resolution Modeling on Arbitrary Meshesxe2x80x9d, 1998.
Examples of mesh simplification algorithms are numerous. First is a progressive mesh that computes a sequence of progressively refineable meshes by successive application of an edge collapse operator. See H. Hoppe, xe2x80x9cProgressive Meshesxe2x80x9d, 1996. In combination with appropriate data structures and error metrics, this method provides a very powerful representation for triangle meshes. Another method uses a vertex removal strategy with a local remeshing method to successively simplify an initially dense mesh. See W. Schrxc3x6der, J. Zarge, and W. Lorensen, xe2x80x9cDecimation of Triangle Meshesxe2x80x9d, 1992.
Mesh fairing is the most efficient way to enhance the smoothness of the mesh after simplification. Unlike geometrically motivated approaches to fairing that involve costly minimization of fairing functionals, G. Taubin uses a signal processing approach to mesh fairing. He is the first to map standard filtering techniques to meshes with arbitrary connectivity. This approach generalizes the notion of xe2x80x9cfrequencyxe2x80x9d to meshes of arbitrary connectivity by taking eigenfunctions of discretized Laplacian operator. Smoothing is accomplished by attenuation of the eigenvalues associated with the xe2x80x9chigh frequenciesxe2x80x9d of the mesh. This type of xe2x80x9clow-passxe2x80x9d filtering band-limits the mesh and produces visually appealing models. Because the storage and computational cost is linear in the number of vertices, this approach is popular for mesh filtering. See, G. Taubin, xe2x80x9cA Signal Processing Approach to Fair Surface Designxe2x80x9d, 1995.
Building on the research of Taubin, the next development uses an implicit fairing method using a backward Euler integration. Rather than using discretized Laplacian operators as the flow operator, a discrete curvature flow operator is used. These enhancements allow the construction of a more robust algorithm to smooth meshes with arbitrary topology and reduce the need of human supervision during the smoothing process. The algorithm also obtains better results, both with respect to the quality of the smoothing and the shape of the triangles in the mesh. See, M. Desbrun, M. Meyer, P. Schrxc3x6der, and A. H. Barr, xe2x80x9cImplicit Fairing of Irregular Meshes using Diffusion and Curvature Flowxe2x80x9d, 1999.
The next development is provided by Guskov and W. Sweldens. They combine non-uniform subdivision with a fairing algorithm to transform an arbitrary mesh into a multi-resolution representation. The details influence the mesh on an increasingly simplified scale with this multi-resolution representation, thereby resulting in an extension of the signal processing approach to triangle meshes. The most important difference between this new approach and the approaches of Taubin and Kobbelt is that the Laplacian operators not only approximate the topological information, but also consider the geometric information.
Different fairing operators may be used when fairing a mesh. A fairing operator is applied to intersected triangle meshes in a manifold or non-manifold model to achieve a smooth model. In rating the overall performance of the different operators, a trade-off between the speed and quality of the operators exists. The faster the operator performs the task, the quality of the operation declines. Also, as the quality of the operation performed by the operator increases, the speed declines since the complexity of the formula to accomplish the fairing requires much additional computational cost. There are four commonly accepted fairing operators. A comparison of the smoothing effect of each of the operators is shown in FIGS. 1A-1E. A non-smoothed sphere (8) is shown in FIG. 1A as a starting point for each of the listed operators. FIG. 1B shows the smoothing effect of an umbrella operator (1). The smoothing effect of the improved umbrella operator (2) is shown in FIG. 1C. The smoothing effect of the curvature flow operator (4) is shown in FIG. 1D. The smoothing effect of the second order divided differences operator (6) is shown in FIG. 1E. The fairing operator with the fastest speed and lowest quality is the improved umbrella operator (2). The best quality results are generated by the curvature flow operator (4) and the second order differences operator (6), but they are also the slower and more complex operators.
In one aspect, the invention is a system and method of fairing a non-manifold model that starts by determining the features of the model. A fairing operator is then applied to the features to smooth the model and remove noise.
An embodiment of the invention includes manipulating triangle meshes that define the non-manifold model at different levels of resolution.
An embodiment of the invention includes a local volume preservation method for models that starts by computing a volume of a tetrahedra defined by a plurality of triangle meshes. The triangle meshes are then moved along a fixed vector. The vertices are moved to compensate for the change in volume caused by the fairing operator while smoothing the model.
An embodiment of the invention includes a feature preservation method for models that starts by distinguishing between noise and the features of the model. The noise is removed and the features in the model are preserved using local operators. During the fairing process, the features are prevented from moving by setting a number of vertices to zero vertices.
Other aspects and advantages of the invention will be apparent from the following description and the appended claims.